/**
 * @a https://leetcode.cn/problems/flood-fill/
 */

#include "../../common.h"


class Solution {
    using PII=pair<int,int>;
    int dx[4] = {1,-1,0,0};
    int dy[4] = {0,0,1,-1};
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int pre_colr = image[sr][sc];
        if(pre_colr == color) return image;
        
        int row = image.size();
        int col = image[0].size();
        
        queue<PII> que;
        que.push({sr,sc});
        while(que.size()){
            auto [x,y] = que.front();
            que.pop();
            image[x][y] = color;
            for(int i = 0; i < 4; ++i){
                int a = x + dx[i];
                int b = y + dy[i];
                if(a >= 0 && a < row && b >= 0 && b < col && pre_colr == image[a][b])
                {
                    que.push({a,b});
                }

            }
        }
        return image;
    }
};